package 力扣面试经典150;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-04-14
 * Time:16:25
 */

/**
 * 力扣面试经典150:77. 组合
 * 中等
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * 你可以按 任何顺序 返回答案。
 * 示例 1：
 * 输入：n = 4, k = 2
 * 输出：
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 */
public class combine {
    List<List<Integer>> res;
    List<Integer> path;
    int n;
    int k;
    public  List<List<Integer>> combine(int _n, int _k) {
        res = new ArrayList<>();
        path = new ArrayList<>();
        n = _n;
        k = _k;
        if(n == 0 || k == 0)return res;
        dfs(1);
        return res;
    }
    public  void dfs(int index){
        if(path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = index;i <= n;i++){
            path.add(i);
            dfs(i + 1);
            path.remove(path.size() - 1);
        }
    }
}
